#include <cstddef>
#include<iostream>
#include <assert.h>
#include <bits/stdc++.h>

void test_malloc() {
  std::cout << sizeof(unsigned long) << std::endl;
  printf("%p\n", sbrk(0));
  char* ptr = (char*)malloc(1024 * 1024 * 1024);
  *ptr = 'a';
  /// 44704字节 还有8字节的大小，所以应该是。。。44712？
  printf("%p\n", sbrk(0));
  printf("%p\n", ptr);
  /// 33个页（4k）
  printf("size: %lu\n", *(unsigned long*)(ptr - 8));
}

void quickSort(std::vector<int>& num, int left, int right) {
  if (left < right) {
    int le = left, ri = right, temp = num[left];
    while(le < ri) {
      while(le < ri && num[ri] >= temp) {
        --ri;
      }
      if (le < ri) {
        num[le] = num[ri];
      }
      while(le < ri && num[le] <= temp) {
        ++le;
      }
      if (le < ri) {
        num[ri] = num[le];
      }
    }
    num[le] = temp;
    quickSort(num, left, le - 1);
    quickSort(num, le + 1, right);
  }
}

void test_quickSort() {
  std::vector<int> arr = {1,6,78,0,4,3,2,6,3, 56, 576,5, 6,35 ,6,};
  quickSort(arr, 0, arr.size());
  for (auto num : arr) {
    printf("%d  ", num);
  }
  printf("\n");
}

template<class T>
class Heap {
public:
  Heap() : _dump([this]() {
    for (int i = 0; i < _size; i++) {
      printf("%d  ", _vec[i]);
    }
    printf("\n");
  }), _cmp([](const T& le, const T& ri) ->bool {
    return le < ri;
  }) {
    _vec.reserve(20);
  }
  typedef std::shared_ptr<Heap> ptr;
  typedef T value;
  typedef T& referValue;
  typedef T* pointerValue;
public:
  void push(const T& value);
  value pop();
  void show();
  value top() { assert(_size > 0); return _vec[0];}
  bool isEmpty() { return _size == 0;}
  int size() { return _size;}
private:
  void adjustUp();
  void adjustDown();
private:
  std::vector<T> _vec;
  std::function<bool(const T& le, const T& ri)> _cmp;
  std::function<void()> _dump;
  int _size{0};
};

template<class T>
void Heap<T>::push(const T& value) {
  if (_size < _vec.capacity()) {
    _vec[_size] = value;
  } else {
    _vec.push_back(value);
  }
  adjustUp();
  ++_size;
  // printf("xxx %d\n", _vec[0]);
}

template<class T>
typename Heap<T>::value Heap<T>::pop() {
  assert(_size > 0);
  std::swap(_vec[0], _vec[--_size]);
  adjustDown();
  return _vec[_size];
}

template<class T>
void Heap<T>::show() {
  _dump();
}

template<class T>
void Heap<T>::adjustDown() {
  int parent = 0;
  int child = parent * 2 + 1;  /// 左孩子
  while(child < _size) {
    /// 如果当前节点存在右孩子且右孩子更小，小根堆把更小的向上层换
    if (child + 1 < _size && _vec[child + 1] > _vec[child]) {
      ++child;
    }
    if (_vec[parent] < _vec[child]) {
      std::swap(_vec[parent], _vec[child]);
      parent = child;
      child = parent * 2 + 1;
    } else {
      break;
    }
  }
}

template<class T>
void Heap<T>::adjustUp() {
   int parent = (_size - 1) / 2;
   int child = _size;
   while(child > 0) {
     if (_vec[parent] < _vec[child]) {
       std::swap(_vec[parent], _vec[child]);
       child = parent;
       parent = (child - 1) / 2;
     } else {
       break;
     }
   }
}

void test_Heap() {
  Heap<int> he;
  he.push(3);
  he.show();
  he.push(5);
  he.push(9);
  he.show();
  he.push(2);
  he.push(4);
  he.show();
  he.push(7);
  he.push(8);
  he.show();
  he.push(1);
  he.show();
  printf("%d\n", he.top());
  he.pop();
  he.show();
  printf("%d\n", he.top());
  he.show();
}


int main() {
  // test_malloc();
  // test_Heap();
  int a = 3;
  int b = 6;
  int const * p = &a;

  const int& t = a;
  int const& tt= a;
  const int &ttt = a;

  return 0;
}